package bfs;

import java.util.*;

public class JumpGameIV1345 {
    //todo
//    public int minJumps(int[] arr) {
//        Map<Integer, TreeSet<Integer>>  map = new HashMap<>();
//        //init
//        for (int i = 0; i < arr.length; i++) {
//            TreeSet<Integer> list = map.getOrDefault(arr[i], new TreeSet<>());
//            list.add(i);
//            map.put(arr[i],list);
//        }
//        //
//        int[] dp = new int[arr.length];
//        dp[0]=0;
//        for (int i = 1; i < dp.length; i++) {
//            TreeSet<Integer> treeSet = map.get(arr[i]);
//            int k = i;
//            while (treeSet.lower(k)!=null){
//                Integer lower = treeSet.lower(k);
//                dp[i]=Math.min(dp[i],dp[lower]+1);
//                k=lower;
//            }
//            dp[i] = Math.min(dp[i],dp[i-1]+1);
//        }
//
//        for (int i = dp.length-2; i >=0 ; i--) {
//            TreeSet<Integer> treeSet = map.get(arr[i]);
//            int k = i;
//            while (treeSet.higher(k)!=null){
//                Integer higher = treeSet.higher(k);
//                dp[i]=Math.min(dp[i],dp[higher]+1);
//                k=higher;
//            }
//            dp[i] = Math.min(dp[i],dp[i-1]+1);
//        }
//        TreeSet<Integer> treeSet = map.get(arr[arr.length-1]);
//        int k = arr.length-1;
//        while (treeSet.lower(k)!=null){
//            Integer lower = treeSet.lower(k);
//            dp[arr.length-1]=Math.min(dp[arr.length-1],dp[lower]+1);
//            k=lower;
//        }
//        dp[arr.length-1] = Math.min(dp[arr.length-1],dp[arr.length-1-1]+1);
//        return dp[dp.length-1];
//
//    }
}
